home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’93 / sort / Source / shakershell.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-17  |  1.9 KB  |  79 lines  |  [TEXT/MPS ]
  1. /*
  2.     shakershell.c
  3.  
  4.     Author: Paul Baxter.
  5.  
  6.     This sort is a combination of a shaker sort and a shell sort.
  7.     This was written just for test purposes only. This is a not a
  8.     standard sort. 
  9.  
  10.     Here is how it works:
  11.  
  12.     1) Set gap as number of data / 2.
  13.     2) Start an incrementing loop (index) from 0 to number of data - gap.
  14.     3) Compare index data item to index + gap data item.
  15.     4) If index data item greater than index + gap data item swap and set flag.
  16.     5) End loop.
  17.     6) If swap flag == false goto 12.
  18.     7) Start an decrementing loop (index) from number of data - gap -1 to 1.
  19.     8) Compare index data item to index - gap data item.
  20.     9) If index data item greater than index + gap data item swap and set flag.
  21.     10) End loop.
  22.     11) If swap flag == true then goto 2.
  23.     12) Set gap to gap / 2.
  24.     13) If gap > 0 then goto 2.
  25.     14) End.
  26. */
  27.  
  28. #ifndef THINK_C
  29. #include <Types.h>
  30. #endif
  31.  
  32. #include "sortdata.h"
  33.  
  34. void main(long maxdata, long* sortdata, swp sw, cmp cm, short* stopflag);
  35.  
  36. void main(long maxdata, long* sortdata, swp sw, cmp cm, short* stopflag)
  37. {
  38.     long gap, index, select, *pindex, *pselect;
  39.     Boolean swaped;
  40.     gap = maxdata >> 1;
  41.     while (gap > 0) {
  42.         do {
  43.             swaped = false;
  44.             pindex = sortdata;
  45.             select = gap;
  46.             pselect = &sortdata[gap];
  47.             for (index = 0; index < maxdata - gap; index++, pindex++, select++, pselect++) {
  48.  
  49.                 if (*stopflag) {
  50.                     return;
  51.                 }
  52.  
  53.                 if ((*cm)(index, select, *pindex, *pselect) > 0) {
  54.                     (*sw)(index, select, pindex, pselect);
  55.                     swaped = true;
  56.                 }
  57.             }
  58.             if (swaped) {
  59.                 swaped = false;
  60.                 index = select - 1;
  61.                 pindex = pselect - 1;
  62.                 select = index - gap;
  63.                 pselect = &sortdata[select];
  64.                 for (; select > 0; index--, pindex--, select--, pselect--) {
  65.                     if (*stopflag) {
  66.                         return;
  67.                     }
  68.     
  69.                     if ((*cm)(index, select, *pindex, *pselect) < 0) {
  70.                         (*sw)(index, select, pindex, pselect);
  71.                         swaped = true;
  72.                     }
  73.                 }
  74.             }
  75.         } while (swaped);
  76.          gap >>= 1;
  77.     }
  78. }
  79.